#
# @lc app=leetcode.cn id=63 lang=python3
#
# [63] 不同路径 II
#

# @lc code=start
class Solution:
    def uniquePathsWithObstacles(self, obstacleGrid: List[List[int]]) -> int:
        # 1.确定状态
        # 最后一步状态:dp[2][2]
        # 子问题:dp[2][2]=dp[2][1]+dp[0][2]
        # 2.状态转移方程
        # dp[i-1][j] = dp[i-1][j] if obstacleGrid[i-1][j]==0 else dp[i-1][j]
        # dp[i][j]=dp[i-1][j]+dp[i][j-1]
        # 3.初始条件和临界情况 细节难点
        # 4.循环顺序
        # i [1,m-1] j [1,n-1]
        m, n = len(obstacleGrid), len(obstacleGrid[0])
        dp = [[1]*n for _ in range(m)]

        if obstacleGrid[0][0] == 1:
            return 0
        # 3.初始条件和临界情况 细节难点
        for i in range(1, m):
            if obstacleGrid[i][0]==1:
                dp[i][0]=0
            else:
                dp[i][0]=dp[i-1][0]
        for j in range(1, n):
            if obstacleGrid[0][j]==1:
                dp[0][j]=0
            else:
                dp[0][j]=dp[0][j-1]
        
        for i in range(1, m):
            for j in range(1, n):
                if obstacleGrid[i][j]==1:
                    dp[i][j]=0
                else:
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
            #     print(f'dp[{i}][{j}] = {dp[i-1][j]} + {dp[i][j-1]}= {dp[i-1][j] + dp[i][j-1]}')
            # print()
        # print(dp)
        return dp[m-1][n-1]
# @lc code=end

